//每次操作去除所有的叶节点，直到只剩不多于两个节点
//直观上来看，越里面的节点作为根节点，树的高度就会越小
import java.util.*;

public class Solution310 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n==1){
            return Collections.singletonList(0);
        }else if (n==2){
            return Arrays.asList(0,1);
        }
        int[] first=new int[n];
        Arrays.fill(first,-1);
        int cur=0;
        int[] next=new int[edges.length*2];
        int[] go=new int[edges.length*2];
        int[] du=new int[n];
        for (int[] edge : edges) {
            next[cur]=first[edge[0]];
            first[edge[0]]=cur;
            go[cur]=edge[1];
            cur++;
            next[cur]=first[edge[1]];
            first[edge[1]]=cur;
            go[cur]=edge[0];
            cur++;
            du[edge[1]]++;
            du[edge[0]]++;
        }
        int res=n;
        Queue<Integer> queue=new LinkedList<>();
        boolean[] visit=new boolean[n];
        for (int i = 0; i < n; i++) {
            if (du[i]==1){
                visit[i]=true;
                queue.offer(i);
                res--;
            }
        }
        while (res>2){
            Queue<Integer> temp=new LinkedList<>();
            while (!queue.isEmpty()) {
                int q = queue.poll();
                int k = first[q];
                while (k != -1) {
                    du[go[k]]--;
                    if (!visit[go[k]] && du[go[k]] == 1) {
                        visit[go[k]] = true;
                        temp.offer(go[k]);
                        res--;
                    }
                    k = next[k];
                }
            }
            queue=temp;
        }
        List<Integer> ans=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!visit[i]){
                ans.add(i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution310().findMinHeightTrees(6,new int[][]{{0,1},{0,2},{0,3},{3,4},{4,5}}));
    }
}
